package com.sheng.leetcode.year2022.swordfingeroffer.day30;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/09/29
 *<p>
 * 剑指 Offer 51. 数组中的逆序对<p>
 *<p>
 * 在数组中的两个数字，如果前面一个数字大于后面的数字，<p>
 * 则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。<p>
 *<p>
 * 示例 1:<p>
 * 输入: [7,5,6,4]<p>
 * 输出: 5<p>
 *<p>
 * 限制：<p>
 * 0 <= 数组长度 <= 50000<p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class Sword0051 {

    @Test
    public void test01() {
        int[] nums = {7,5,6,4};
        System.out.println(new Solution51().reversePairs(nums));
    }
}
// 暴力破解，超时
//class Solution51 {
//    public int reversePairs(int[] nums) {
//        int count = 0;
//        int length = nums.length;
//        for (int i = 0; i < length; i++) {
//            for (int j = i + 1; j < length; j++) {
//                if (nums[i] > nums[j]) {
//                    count++;
//                }
//            }
//        }
//        return count;
//    }
//}

class Solution51 {

    public int reversePairs(int[] nums) {
        // 分治法
        int len = nums.length;
        // 数组长度小余2时，直接返回
        if (len < 2) {
            return 0;
        }
        // 创建一个copy数组，赋值nums数组中的元素
        int[] copy = new int[len];
        for (int i = 0; i < len; i++) {
            copy[i] = nums[i];
        }
        // 临时数组temp
        int[] temp = new int[len];
        return reversePairs(copy, 0, len - 1, temp);
    }

    /**
     * nums[left..right] 计算逆序对个数并且排序
     *
     * @param nums
     * @param left
     * @param right
     * @param temp
     * @return
     */
    private int reversePairs(int[] nums, int left, int right, int[] temp) {
        // 左右边界相等，返回0
        if (left == right) {
            return 0;
        }

        // 获取左右边界的中间值
        int mid = left + (right - left) / 2;
        // 分别对左右两个子数组范围进行计算
        int leftPairs = reversePairs(nums, left, mid, temp);
        int rightPairs = reversePairs(nums, mid + 1, right, temp);

        // 如果整个数组已经有序，则无需合并，注意这里使用小于等于
        if (nums[mid] <= nums[mid + 1]) {
            return leftPairs + rightPairs;
        }

        int crossPairs = mergeAndCount(nums, left, mid, right, temp);
        return leftPairs + rightPairs + crossPairs;
    }

    /**
     * nums[left..mid] 有序，nums[mid + 1..right] 有序
     *
     * @param nums
     * @param left
     * @param mid
     * @param right
     * @param temp
     * @return
     */
    private int mergeAndCount(int[] nums, int left, int mid, int right, int[] temp) {
        // 将数组中的元素存放到临时数组temp中
        for (int i = left; i <= right; i++) {
            temp[i] = nums[i];
        }
        // i为左子数组的左边界
        int i = left;
        // j为左子数组的右边界
        int j = mid + 1;

        int count = 0;
        for (int k = left; k <= right; k++) {
            // 有下标访问，得先判断是否越界
            if (i == mid + 1) {
                nums[k] = temp[j];
                j++;
            } else if (j == right + 1) {
                nums[k] = temp[i];
                i++;
            } else if (temp[i] <= temp[j]) {
                // 注意：这里是 <= ，写成 < 就不对，请思考原因
                nums[k] = temp[i];
                i++;
            } else {
                nums[k] = temp[j];
                j++;

                // 在 j 指向的元素归并回去的时候，计算逆序对的个数，只多了这一行代码
                count += (mid - i + 1);
            }
        }
        return count;
    }
}
//
//作者：liweiwei1419
//链接：https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/bao-li-jie-fa-fen-zhi-si-xiang-shu-zhuang-shu-zu-b/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
